\mode<article>{\usepackage{fullpage}}

\usepackage{listings}
\lstset{language=Java,
        basicstyle=\small}

\usepackage{graphicx}
\usepackage{hyperref}

\hypersetup{
  colorlinks=true,
  urlcolor=blue,
  linkcolor=black
}

\title{Building A Graph Library}
\author{Matt Bone}
\date{\today}

\begin{document}

\mode<article>{\maketitle}
%\tableofcontents
%\mode<article>{\pagebreak}
\mode<article>{\setlength{\parskip}{.25cm}}
\mode<presentation>{\frame{\titlepage}}
\mode<all>{\bibliographystyle{abbrvnat}}

\begin{frame}[fragile]
If we set out to build a graph library, we must first ask ourselves, how will we represent the graph?
\end{frame}


\begin{frame}[fragile]
Really?
\end{frame}


\begin{frame}[fragile]
We don't actually need to make this decision right away.
\end{frame}


\begin{frame}[fragile]
OOP is all about delaying decisions.
\end{frame}


\begin{frame}[fragile]
So let's think about the classes we need first.
\end{frame}


\begin{frame}[fragile]
This is a pretty well defined problem, so we know what classes we will need.
\end{frame}


\begin{frame}[fragile]
A \verb'Graph' class.
\end{frame}

\begin{frame}[fragile]
An \verb'Edge' class.
\end{frame}

\begin{frame}[fragile]
A \verb'Node' class.
\end{frame}


\begin{frame}[fragile]
To simplify things, let's agree that we will only \textbf{add} edges and nodes to a graph.
\end{frame}


\begin{frame}[fragile]
Removal is an exercise for the reader.
\end{frame}


\begin{frame}[fragile]
Let us also restrict ourselves to undirected, unweighted graphs for now.
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
public class Graph {

  public void addNode(Node n) { ... }

  public void addEdge(Node u, Node v) { ... }

  public List<Node> getAdjacentNodes(Node n) { ... }

}
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
What information do we need in the \verb'Node' class to make it useful?
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
public class Node {
  String label;
}
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
What information do we need in the \verb'Edge' class to make it useful?
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
public class Edge {
  ???
}
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
What belongs in the \verb'Edge' class depends on how we represent the graph.
\end{frame}


\begin{frame}[fragile]
Perhaps we can no longer delay our decisions.
\end{frame}


\begin{frame}[fragile]
Let's use an adjacency list representation.
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
public class Graph {

  public HashMap<Node, List<Node>> adjacencies;

  public void addNode(Node n) { ... }

  public void addEdge(Node u, Node v) { ... }

  public List<Node> getAdjacentNodes(Node n) { ... }

}
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
What are the \emph{preconditions} of \verb'addEdge'?
\end{frame}


\begin{frame}[fragile]
Both nodes must be in the graph.
\end{frame}


\begin{frame}[fragile]
What are the \emph{preconditions} of \verb'addNode'?
\end{frame}


\begin{frame}[fragile]
The node must not be in the graph.
\end{frame}


\begin{frame}[fragile]
What are the \emph{postconditions} of \verb'addNode'?
\end{frame}


\begin{frame}[fragile]
The node is in the graph, in adjacencies with an empty list.
\end{frame}


\begin{frame}[fragile]
What are the \emph{postconditions} of \verb'addEdge'?
\end{frame}


\begin{frame}[fragile]
Each node is in the other's adjacency list.
\end{frame}


\begin{frame}[fragile]
So what does \verb'addNode' look like?
\end{frame}


\begin{frame}[fragile]
And what does \verb'addEdge' look like?
\end{frame}


%\begin{frame}[fragile]
%How do we implement something like a Dijstra's Algorithm?
%\end{frame}
%\begin{frame}[fragile]
%What should the algorithm take as a parameter?
%\end{frame}
%\begin{frame}[fragile]
%A \verb'Graph' and a source \verb'Node'.
%\end{frame}
%\begin{frame}[fragile]
%What should the algorithm return?
%\end{frame}
%\begin{frame}[fragile]
%A new graph.
%\end{frame}

\begin{frame}[fragile]
Remember, graphs are trees.
\end{frame}


\begin{frame}[fragile]
Let's draw a tree with our library.
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
  Graph t = new Graph();a
  
  Node a = new Node("a");
  Node b = new Node("b");
  Node c = new Node("c");
  Node d = new Node("d");
  
  t.addNode(a).addNode(b).addNode(c).addNode(d);
  t.addEdge(a, b).addEdge(a, c).addEdge(a, d);
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
How can we print it out?
\end{frame}


\begin{frame}[fragile]
We'll use s-expressions to draw the graph.
\end{frame}


\begin{frame}[fragile]
The tree:
\begin{verbatim}
  4
 / \
6   7
   / \
  8   9
\end{verbatim}
is represented as:
\begin{verbatim}
(4 (6) (7 (8) (9)))
\end{verbatim}
\end{frame}


\begin{frame}[fragile]
A DFS algorithm.
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
//only meaningful if run on a non-tree graph
public static 
    String printGraphAsTree(Graph n, 
                            Node source, 
                            HashSet<Node> seen) {
  seen.add(source);
  
  String children="";
  
  for(Node child: n.getAdjacentNodes(source)) {
    if(!seen.contains(child))
      children+=printGraphAsTree(n, child, seen) + " ";
  }
  
  children = children.trim();
  if(children!="")
    return "("+source.getLabel()+" "+children+")";
  return "("+source.getLabel()+")";
}
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
Again, this is only meaningful for the subset of graphs that are trees.
\end{frame}

\begin{frame}[fragile]
Now for questions I haven't answered.
\end{frame}


\begin{frame}[fragile]
What if we want to represent directed edges?
\end{frame}


\begin{frame}[fragile]
What if we want to use an adjacency matrix?
\end{frame}


\begin{frame}[fragile]
What if we want to represent weighted edges?
\end{frame}


\end{document}
